home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 425_01 / tar / lzpack.c < prev    next >
Encoding:
C/C++ Source or Header  |  1980-07-23  |  14.8 KB  |  526 lines
  1. /* lzpack.c - compress encode/decode file for Tar program (see file tar.c)
  2.  * Programmer: T.V.Shaporev
  3.  * Prepared for release 19 Oct 1990
  4.  * Called by store() (see file store.c) and extract() (see file extract.c)
  5.  */
  6. /* Source:
  7.  *    LZARI.C -- A Data Compression Program
  8.  *    4/7/1989 Haruhiko Okumura
  9.  *    PC-VAN        SCIENCE
  10.  *    NIFTY-Serve    PAF01022
  11.  *    CompuServe    74050,1022
  12.  */
  13.  
  14. /* Modified 30.9.90 Tim Shaporev */
  15.  
  16. #include "sysup.h"
  17.  
  18. extern char v_flag;
  19.  
  20. #include <stdio.h>
  21.  
  22. #ifdef UNIX
  23.     char *malloc();
  24.     void free();
  25. #endif
  26.  
  27. #ifdef MSDOS
  28. #    include <stdlib.h>
  29. #endif
  30.  
  31. #define    pare(x)  ((x)<<1)
  32. #define half(x)  ((x)>>1)
  33.  
  34. #include "sysup.h"
  35.  
  36. #ifdef MSDOS
  37. #    define __ARGS__(x) x
  38. #endif
  39. #ifndef __ARGS__
  40. #    define __ARGS__(x) ()
  41. #endif
  42.  
  43. #include "lzpack.h"
  44.  
  45. static  void    PutBit        __ARGS__(( int ));
  46. static  void    FlushBitBuffer    __ARGS__(( void ));
  47. static  int    GetBit        __ARGS__(( void ));
  48. static  int    InitTree    __ARGS__(( void ));
  49. static  void    InsertNode    __ARGS__(( int ));
  50. static  void    DeleteNode    __ARGS__(( int ));
  51. static  void    StartModel    __ARGS__(( void ));
  52. static  void    UpdateModel    __ARGS__(( int ));
  53. static  void    Output        __ARGS__(( int ));
  54. static  void    EncodeChar    __ARGS__(( int ));
  55. static  void    EncodePosition    __ARGS__(( int ));
  56. static  void    EncodeEnd     __ARGS__(( void ));
  57. static  int    BinarySearchSym    __ARGS__(( unsigned ));
  58. static  int    BinarySearchPos    __ARGS__(( unsigned ));
  59. static  void    StartDecode    __ARGS__(( void ));
  60. static  int    DecodeChar    __ARGS__(( void ));
  61. static  int    DecodePosition    __ARGS__(( void ));
  62.  
  63. /********** Bit I/O **********/
  64. static short PutBuf, PutMask;
  65.  
  66. #define InitPutBit (PutBuf=0, PutMask = 128)
  67.  
  68. static int  (*getbyte) __ARGS__(( void ));
  69. static void (*putbyte) __ARGS__(( int ));
  70.  
  71. static void PutBit(bit)  /* Output one bit (bit = 0,1) */
  72. register bit;
  73. {
  74.    if (bit) PutBuf |= PutMask;
  75.    if ((PutMask >>= 1) == 0) {
  76.       (*putbyte)((int)PutBuf);
  77.       InitPutBit;
  78.    }
  79. }
  80.  
  81. static void FlushBitBuffer()  /* Send remaining bits */
  82. {
  83.    if (PutMask != 128) (*putbyte)((int)PutBuf);
  84. }
  85.  
  86. static short GetBuf, GetMask;
  87.  
  88. #define InitGetBit (GetMask=0)
  89.  
  90. static int GetBit()  /* Get one bit (0 or 1) */
  91. {
  92.    if ((GetMask >>= 1) == 0) {
  93.       GetBuf = (*getbyte)();
  94.       GetMask = 128;
  95.    }
  96.    return (GetBuf & GetMask) != 0;
  97. }
  98.  
  99. /********** LZSS with multiple binary trees **********/
  100. #define N         4096    /* size of ring buffer */
  101. #define F           60    /* upper limit for match_length */
  102. #define THRESHOLD    2    /* encode string into position and length */
  103.                           /* if match_length is greater than this */
  104. #define NIL          N    /* index for root of binary search trees */
  105.  
  106. /* ring buffer of size N, with extra F-1 bytes for string comparison */
  107. /* unsigned char text_buf[N+F-1]; */
  108.  
  109. short match_position, match_length; /* of longest match. */
  110. /* These are set by the InsertNode() procedure. */
  111.  
  112. /* short lson[N+1], rson[N+257], dad[N+1]; */
  113. /* left & right children & parents -- These constitute binary search trees. */
  114.  
  115. static short *core = (short *)0;
  116.  
  117. #define position_cum ((unsigned short *)core)
  118. #define lson         (core + N+1)
  119. #define rson         (core + N+1 + N+1)
  120. #define dad         (core + N+1 + N+1 + N+257)
  121. #define text_buf ((unsigned char *)(core + N+1 + N+1 + N+257 + N+1))
  122.  
  123. int lzgetmem()
  124. {
  125.    if (!core) {
  126.       core=(short*)malloc((N+1 + N+1 + N+257 + N+1) * sizeof(short) + N+F);
  127.       if (!core) return -1;
  128.    }
  129.    return 0;
  130. }
  131.  
  132. void lzrelmem()
  133. {
  134.    if (core) free((char *)core); core = (short *)0;
  135. }
  136.  
  137. static int InitTree()  /* Initialize trees */
  138. {
  139.     register int i;
  140.  
  141.     /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  142.        left children of node i.  These nodes need not be initialized.
  143.        Also, dad[i] is the parent of node i.  These are initialized to
  144.        NIL (= N), which stands for 'not used.'
  145.        For i = 0 to 255, rson[N + i + 1] is the root of the tree
  146.        for strings that begin with character i.  These are initialized
  147.        to NIL.  Note there are 256 trees. */
  148.     if (!core) return -1;
  149.  
  150.     for (i=N+1; i<=N+256; i++) rson[i] = NIL;    /* root */
  151.     for (i=0; i<N; i++)        dad[i] = NIL;    /* node */
  152.     return 0;
  153. }
  154.  
  155. static void InsertNode(r)
  156. register int r;
  157. /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  158.    trees (text_buf[r]'th tree) and returns the longest-match position
  159.    and length via the global variables match_position and match_length.
  160.    If match_length = F, then removes the old node in favor of the new
  161.    one, because the old one will be deleted sooner.
  162.    Note r plays double role, as tree node and position in buffer. */
  163. {
  164.     register int p;
  165.     register int i;
  166.     register int cmp, temp;
  167.     register unsigned char *key;
  168.  
  169.     cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  170.     rson[r] = lson[r] = NIL;  match_length = 0;
  171.     for ( ; ; ) {
  172.         if (cmp >= 0) {
  173.             if (rson[p] != NIL) p = rson[p];
  174.             else {  rson[p] = r;  dad[r] = p;  return;  }
  175.         } else {
  176.             if (lson[p] != NIL) p = lson[p];
  177.             else {  lson[p] = r;  dad[r] = p;  return;  }
  178.         }
  179.         for (i = 1; i < F; i++)
  180.             if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  181.         if (i > THRESHOLD) {
  182.             if (i > match_length) {
  183.                 match_position = (r - p) & (N - 1);
  184.                 if ((match_length = i) >= F) break;
  185.             } else if (i == match_length) {
  186.                 if ((temp = (r - p) & (N - 1)) < match_position)
  187.                     match_position = temp;
  188.             }
  189.         }
  190.     }
  191.     dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  192.     dad[lson[p]] = r;  dad[rson[p]] = r;
  193.     if (rson[dad[p]] == p) rson[dad[p]] = r;
  194.     else                   lson[dad[p]] = r;
  195.     dad[p] = NIL;  /* remove p */
  196. }
  197.  
  198. static void DeleteNode(p)  /* Delete node p from tree */
  199. register int p;
  200. {
  201.    register int q;
  202.  
  203.    if (dad[p] == NIL) return;  /* not in tree */
  204.    if (rson[p] == NIL) q = lson[p];
  205.    else if (lson[p] == NIL) q = rson[p];
  206.    else {
  207.       q = lson[p];
  208.       if (rson[q] != NIL) {
  209.          do {  q = rson[q];  } while (rson[q] != NIL);
  210.          rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
  211.          lson[q] = lson[p];  dad[lson[p]] = q;
  212.       }
  213.       rson[q] = rson[p];  dad[rson[p]] = q;
  214.    }
  215.    dad[q] = dad[p];
  216.    if (rson[dad[p]] == p) rson[dad[p]] = q;
  217.    else                   lson[dad[p]] = q;
  218.    dad[p] = NIL;
  219. }
  220.  
  221. /********** Arithmetic Compression **********/
  222.  
  223. /*  If you are not familiar with arithmetic compression, you should read
  224.         I. E. Witten, R. M. Neal, and J. G. Cleary,
  225.             Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  226.     from which much have been borrowed.  */
  227.  
  228. #define M   15
  229.  
  230. /*    Q1 (= 2 to the M) must be sufficiently large, but not so
  231.     large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */
  232.  
  233. #define Q1  (1L << M)
  234. #define Q2  (2 * Q1)
  235. #define Q3  (3 * Q1)
  236. #define Q4  (4 * Q1)
  237. #define MAX_CUM (Q1 - 1)
  238.  
  239. #define N_CHAR  (256 - THRESHOLD + F)
  240.     /* character code = 0, 1, ..., N_CHAR - 1 */
  241.  
  242. unsigned long /*int*/  low = 0, high = Q4, value = 0;
  243. short shifts = 0;  /* counts for magnifying low and high around Q2 */
  244. short char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  245. unsigned short sym_freq[N_CHAR + 1];  /* frequency for symbols */
  246. unsigned short sym_cum[N_CHAR + 1];   /* cumulative freq for symbols */
  247. #if 0
  248. unsigned short position_cum[N + 1];   /* cumulative freq for positions */
  249. #endif
  250.  
  251. static void StartModel()  /* Initialize model */
  252. {
  253.    register i; register ch, sym;
  254.  
  255.    sym_cum[N_CHAR] = 0;
  256.    for (sym = N_CHAR; sym >= 1; sym--) {
  257.       ch = sym - 1;
  258.       char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
  259.       sym_freq[sym] = 1;
  260.       sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
  261.    }
  262.    sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
  263.    position_cum[N] = 0;
  264.    for (i = N; i >= 1; i--)
  265.       position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
  266.    /* empirical distribution function (quite tentative) */
  267.    /* Please devise a better mechanism! */
  268. }
  269.  
  270. static void UpdateModel(sym)
  271. register int sym;
  272. {
  273.    register i; register c; register ch_i, ch_sym;
  274.  
  275.     if (sym_cum[0] >= MAX_CUM) {
  276.         c = 0;
  277.         for (i = N_CHAR; i > 0; i--) {
  278.             sym_cum[i] = c;
  279.             c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
  280.         }
  281.         sym_cum[0] = c;
  282.     }
  283.     for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
  284.     if (i < sym) {
  285.         ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
  286.         sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
  287.         char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
  288.     }
  289.     sym_freq[i]++;
  290.     while (--i >= 0) sym_cum[i]++;
  291. }
  292.  
  293. static void Output(bit) /* Output 1 bit, followed by its complements */
  294. register bit;
  295. {
  296.    PutBit(bit); for (; shifts > 0; shifts--) PutBit(!bit);
  297. }
  298.  
  299. static void EncodeChar(ch)
  300. int ch;
  301. {
  302.    register int  sym;
  303.    register unsigned long range;
  304.  
  305.    sym = char_to_sym[ch];
  306.    range = high - low;
  307.    high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  308.    low +=       (range * sym_cum[sym    ]) / sym_cum[0];
  309.    for (;;) {
  310.       if (high <= Q2) {
  311.          Output(0);
  312.       } else if (low >= Q2) {
  313.          Output(1);
  314.          low -= Q2;  high -= Q2;
  315.       } else if (low >= Q1 && high <= Q3) {
  316.          shifts++;  low -= Q1;  high -= Q1;
  317.       } else break;
  318.       low += low;  high += high;
  319.    }
  320.    UpdateModel(sym);
  321. }
  322.  
  323. static void EncodePosition(position)
  324. int position;
  325. {
  326.    register unsigned long int  range;
  327.  
  328.    range = high - low;
  329.    high = low + (range * position_cum[position    ]) / position_cum[0];
  330.    low +=       (range * position_cum[position + 1]) / position_cum[0];
  331.    for (;;) {
  332.       if (high <= Q2) {
  333.          Output(0);
  334.       } else if (low >= Q2) {
  335.          Output(1);
  336.          low -= Q2;  high -= Q2;
  337.       } else if (low >= Q1 && high <= Q3) {
  338.          shifts++;  low -= Q1;  high -= Q1;
  339.       } else break;
  340.       low += low;  high += high;
  341.    }
  342. }
  343.  
  344. static void EncodeEnd()
  345. {
  346.    shifts++;
  347.    Output(low>=Q1);
  348.    FlushBitBuffer();
  349. }
  350.  
  351. static int BinarySearchSym(x)
  352. register unsigned int x;
  353. /* 1      if x >= sym_cum[1],
  354.    N_CHAR if sym_cum[N_CHAR] > x,
  355.    i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
  356. {
  357.     register i; register j; register k;
  358.  
  359.     i = 1;  j = N_CHAR;
  360.     while (i<j) if (sym_cum[k=half(i+j)] > x) i=k+1; else j=k;
  361.     return i;
  362. }
  363.  
  364. static int BinarySearchPos(x)
  365. register unsigned int x;
  366. /* 0 if x >= position_cum[1],
  367.    N - 1 if position_cum[N] > x,
  368.    i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
  369. {
  370.     register i; register j; register k;
  371.  
  372.     i = 1;  j = N;
  373.     while (i<j) if (position_cum[k = half(i+j)] > x) i=k+1; else j=k;
  374.     return i-1;
  375. }
  376.  
  377. static void StartDecode()
  378. {
  379.     register i;
  380.  
  381.     for (i=0; i<M+2; i++) {
  382.        value = pare(value) + GetBit();
  383.     }
  384. }
  385.  
  386. static int DecodeChar()
  387. {
  388.     register unsigned long range;
  389.     register sym, ch;
  390.  
  391.     range = high - low;
  392.     sym = BinarySearchSym((unsigned int)
  393.         (((value - low + 1) * sym_cum[0] - 1) / range));
  394.     high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  395.     low +=       (range * sym_cum[sym    ]) / sym_cum[0];
  396.     for (;;) {
  397.         if (low >= Q2) {
  398.             value -= Q2;  low -= Q2;  high -= Q2;
  399.         } else if (low >= Q1 && high <= Q3) {
  400.             value -= Q1;  low -= Q1;  high -= Q1;
  401.         } else if (high > Q2) break;
  402.         low += low;  high += high;
  403.         value = pare(value) + GetBit();
  404.     }
  405.     ch = sym_to_char[sym];
  406.     UpdateModel(sym);
  407.     return ch;
  408. }
  409.  
  410. static int DecodePosition()
  411. {
  412.     register unsigned long range;
  413.     register position;
  414.  
  415.     range = high - low;
  416.     position = BinarySearchPos((unsigned int)
  417.         (((value - low + 1) * position_cum[0] - 1) / range));
  418.     high = low + (range * position_cum[position    ]) / position_cum[0];
  419.     low +=       (range * position_cum[position + 1]) / position_cum[0];
  420.     for (;;) {
  421.         if (low >= Q2) {
  422.             value -= Q2;  low -= Q2;  high -= Q2;
  423.         } else if (low >= Q1 && high <= Q3) {
  424.             value -= Q1;  low -= Q1;  high -= Q1;
  425.         } else if (high > Q2) break;
  426.         low += low;  high += high;
  427.         value = pare(value) + GetBit();
  428.     }
  429.     return position;
  430. }
  431.  
  432. /********** Encode and Decode **********/
  433.  
  434. long lzencode(fget, fput)
  435. int  (*fget) __ARGS__ ((void));
  436. void (*fput) __ARGS__ ((int));
  437. {
  438.    register i; register r; register s; register c; register len;
  439.    register last_match_length;
  440.    register long textsize;
  441.  
  442.    getbyte = fget; putbyte = fput;
  443.    textsize = 0;
  444.  
  445.    low = 0; high = Q4; value = 0; shifts = 0;
  446.    InitGetBit; InitPutBit;
  447.  
  448.    StartModel();
  449.    if (InitTree() != 0) return -1L;
  450.    s = 0;  r = N - F;
  451.    for (i = s; i < r; i++) text_buf[i] = ' ';
  452.    for (len=0; len < F && (c=getbyte()) != EOF; len++)
  453.       text_buf[r + len] = c;
  454.    textsize = len;
  455.    for (i=1; i<=F; i++) InsertNode(r-i);
  456.    InsertNode(r);
  457.    do {
  458.       if (match_length > len) match_length = len;
  459.       if (match_length <= THRESHOLD) {
  460.          match_length = 1;
  461.          EncodeChar((int)text_buf[r]);
  462.       } else {
  463.          EncodeChar(255-THRESHOLD+match_length);
  464.          EncodePosition(match_position - 1);
  465.       }
  466.       last_match_length = match_length;
  467.       for (i=0; i<last_match_length && (c = getbyte())!=EOF; i++) {
  468.          DeleteNode(s);  text_buf[s] = c;
  469.          if (s < F - 1) text_buf[s + N] = c;
  470.          s = (s + 1) & (N - 1);
  471.          r = (r + 1) & (N - 1);
  472.          InsertNode(r);
  473.       }
  474.       textsize += i;
  475.       while (i++ < last_match_length) {
  476.          DeleteNode(s);
  477.          s = (s + 1) & (N - 1);
  478.          r = (r + 1) & (N - 1);
  479.          if (--len) InsertNode(r);
  480.       }
  481.    } while (len > 0);
  482.    EncodeEnd();
  483.    return textsize;
  484. }
  485.  
  486. long lzdecode(fget, fput, textsize)
  487. /* Attemt to read after end of file IS NOT ERROR !!! Horror */
  488. int  (*fget) __ARGS__ ((void));
  489. void (*fput) __ARGS__ ((int));
  490. long textsize;
  491. {
  492.    register i; register k; register r; register c; register j;
  493.    register unsigned long count;
  494.  
  495.    getbyte = fget; putbyte = fput;
  496.  
  497.    low = 0; high = Q4; value = 0; shifts = 0;
  498.    InitGetBit; InitPutBit;
  499.  
  500.    count = 0;
  501.    StartDecode();
  502.    StartModel();
  503.    for (i=0; i<N-F; i++) text_buf[i] = ' ';
  504.    r = N-F;
  505.    while (count < textsize) {
  506.       if ((c = DecodeChar()) < 256) {
  507.          (*putbyte)(c);
  508.          text_buf[r++] = c;
  509.          r &= N-1;
  510.          count++;
  511.       } else {
  512.          i = DecodePosition();
  513.          i = (r - i - 1) & (N-1);
  514.          j = c - 255 + THRESHOLD;
  515.          for (k=0; k<j; k++) {
  516.             c = text_buf[(i+k) & (N-1)];
  517.             (*putbyte)(c);
  518.             text_buf[r++] = c;
  519.             r &= N-1;
  520.             count++;
  521.          }
  522.       }
  523.    }
  524.    return count;
  525. }
  526.